Users of an online service provider who do not have a direct relationship to one another may nevertheless be linked to one another through intermediate entities based on a personal, business or other relationship among the users and the intermediate entities. For example, a user A may have a friend, user B, who also uses that same online service provider and who has a business relationship with user C who also uses the same online service provider. Thus, user A is linked to user C through user B. Such interpersonal interactions or relationships may generally be referred to as a social network. The number of intermediate entities needed to link one entity/user to another may generally be referred to as the degrees of separation between those two entities/users. The social network may be tracked and maintained by the online service provider. The online service provider may generate a social network by observing which users communicate with one another, may build it from user created contact lists or address books, or may ask the users to explicitly create their networks. Social networks may also provide a mechanism for tracking online reputations, and help the users estimate how much to trust one another.